#include<vector>
using namespace std;


class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        return dfs(m, n, k, 0, 0, visited);
    }

    int dfs(int m, int n, int k, int i, int j, vector<vector<bool>> &visited){
        if(i<0 || i>=m || j<0|| j>=n || visited[i][j] || numCount(i,j)>k){
            return 0;
        }
        visited[i][j] = true;

        return 1 + dfs(m, n, k, i-1, j, visited) + dfs(m, n, k, i+1, j, visited) + dfs(m, n, k, i, j-1, visited) + dfs(m, n, k, i, j+1,visited);

    }

    int numCount(int m, int n){
        int sum = 0;
        while (m>0)
        {
            sum += m%10;
            m = m/10;
        }
        while(n>0){
            sum+=n%10;
            n=n/10;
        }
        return sum;
    }
};